package com.zyk.problem;

import java.util.HashMap;
import java.util.Map;

/**
 * @author zhangsan
 * @date 2021/5/16 10:17
 */
public class LongestLengthOfSubArraySumEqualK {

    // 非负数组
    public static int longestLen1(int[] nums, int K) {
        if (nums == null || nums.length == 0)
            return 0;
        int l = 0, r = 0, sum = nums[0], N = nums.length;
        int ans = -1;
        while (r < N) {
            if (sum == K) {
                ans = Math.max(ans, ++r - l);   // 收集答案, 右往后扩
                if (r == N) break;
                sum += nums[r];
            } else if (sum < K) {
                if (++r == N) break;
                sum += nums[r];   // 右往后扩
            } else {
                sum -= nums[l++];   // 左往后扩
            }
        }
        return ans;
    }

    // 可能有负数的数组
    public static int longestLen2(int[] nums, int K) {
        if (nums == null || nums.length == 0)
            return 0;
        Map<Integer, Integer> map = new HashMap<>();    // 前缀和为key的数, 最早出现的位置value
        map.put(0, -1);
        int sum = 0, N = nums.length;
        int ans = -1;
        for (int i = 0; i < N; i++) {
            sum += nums[i];
            int key = sum - K;
            if (map.containsKey(key)) {     // 之前有前缀和为这个的位置, 统计答案
                ans = Math.max(ans, (i - map.get(key)));
            }
            if (!map.containsKey(sum)) {    // 走的时候别忘记把自己放进去
                map.put(sum, i);
            }
        }
        return ans;
    }


    public static void main(String[] args) {
        /*int[] arr = {3, 2, 1, 3, 3, 1, 1, 1, 1, 1, 1, 2, 2, 2};
        int K = 6;
        System.out.println(longestLen1(arr, K));*/
        int[] arr = {7, 2, 3, 5, -5, 3, 2};
        int K = 10;
        System.out.println(longestLen2(arr, K));
    }

}
